package mo.tags.trie;

class Trie {

    private Trie[] children = new Trie[26];
    private boolean end;

    public Trie() {
    }
    
    public void insert(String word) {
        Trie parent = this;
        int len = word.length();
        for (int i = 0; i < len; i++) {
            parent = insert(word.charAt(i), parent, i == len-1);
        }
    }
    
    public boolean search(String word) {
        Trie trie = find(word);
        return trie != null && trie.end;
    }
    
    public boolean startsWith(String prefix) {
        Trie trie = find(prefix);
        return trie != null;
    }

    private Trie find(String word) {
        Trie cur = this;
        for (int i = 0; i < word.length(); i++) {
            Trie[] children = cur.children;
            if (children[word.charAt(i)-'a'] == null) {
                return null;
            }
            cur = children[word.charAt(i)-'a'];
        }
        return cur;
    }

    private Trie insert(char c, Trie root, boolean end) {
        Trie[] children = root.children;
        Trie trie = children[c-'a'];
        if (trie == null) {
            trie = new Trie();
            children[c-'a'] = trie;
        }
        if (end) {
            trie.end = true;
        }
        return trie;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("app");
        System.out.println(trie.search("apps"));
        System.out.println(trie.search("app"));
    }
}